package com.dycong.common.leetcode.yi.weizhong;

import java.time.LocalDateTime;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-08-13
 * Time: 12:45
 */
public class GreatestCommonDivsor {


    public static void main(String[] args) {
        Set<Integer> sizes = new HashSet<>();
        System.out.println(greatestCommonDivsor_(25, 15));

        LocalDateTime localDateTime = LocalDateTime.now();

        ExecutorService executors = Executors.newFixedThreadPool(50);


    }

    class MyRun implements Runnable {

        @Override
        public void run() {

        }
    }


    /**
     * 更相减损术
     * <p>
     * 出自于中国古代的《九章算术》，也是一种求最大公约数的算法。
     * <p>
     * 他的原理更加简单：
     * <p>
     * 两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。比如10和25，25减去10的差是15,那么10和25的最大公约数，等同于10和15的最大公约数。
     * <p>
     * 由此，我们同样可以通过递归来简化问题。首先，我们先计算出a和b的差值c（假设a>b），把问题转化成求出b和c的最大公约数；然后计算出c和b的差值d（假设c>b），把问题转化成求出b和d的最大公约数；再然后计算出b和d的差值e（假设b>d），把问题转化成求出d和e的最大公约数......
     *
     * @param a
     * @param b
     * @return
     */
    public static Integer getGreatestCommonDivsor(Integer a, Integer b) {
        int bigger = a > b ? a : b;
        int smaller = a < b ? a : b;
        if (bigger % smaller == 0) {
            return smaller;
        }

        return getGreatestCommonDivsor(bigger - smaller, smaller);
    }

    public static int greatestCommonDivsor_(int i, int j) {
        int bigger = Math.max(i, j);
        int smaller = Math.min(i, j);
        if (bigger % smaller == 0) {
            return smaller;
        }
        return greatestCommonDivsor_(bigger - smaller, smaller);

    }
}
